package com.example.demo.sort;

/**
 * 希尔排序
 */
public class ShellSort {

    public static void sort(int[] arr) {
        //每次按照2的除数缩量
        for (int mid = arr.length / 2; mid > 0; mid = mid / 2) {
            for (int i = mid; i < arr.length; i++) {
                //暂存要排序的值
                int tmp = arr[i];
                //已排序的起始位置
                int j = i - mid;
                //从已经排序的序列最右边的开始比较，找到比其小的数，比其大的往后移动
                while (j >= 0 && tmp < arr[j]) {
                    arr[j + mid] = arr[j];
                    j -= mid;
                }
                if (i != j) {
                    arr[j + mid] = tmp;
                }
            }

        }
    }
}
